{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Product of Three Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三个数的最大乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整型数组 <code>nums</code> ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4]\n",
    "<strong>输出：</strong>24\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,-2,-3]\n",
    "<strong>输出：</strong>-6\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 <= nums.length <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 <= nums[i] <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-product-of-three-numbers](https://leetcode.cn/problems/maximum-product-of-three-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-product-of-three-numbers](https://leetcode.cn/problems/maximum-product-of-three-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[1,2,3,4]', '[-1,-2,-3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % MOD\n",
    "        return ans                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        while k:\n",
    "            t = heapq.heappop(nums)\n",
    "            t += 1\n",
    "            heapq.heappush(nums, t)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans *= x\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # if len(nums) < 2:\n",
    "        #     return nums[0] + k\n",
    "        # if max(nums) == min(nums):\n",
    "        #     n = len(nums)\n",
    "        #     a, b = k//n, k%n \n",
    "        #     res = 1\n",
    "        #     for i, num in enumerate(nums):\n",
    "        #         if i < b:\n",
    "        #             res *= num + a + 1\n",
    "        #         else:\n",
    "        #             res *= num + a\n",
    "        #         res = res % (10**9+7)\n",
    "        #     return res\n",
    "        # nums_heap = heapify(nums)\n",
    "        # while k:\n",
    "        #     a, b = heappop(nums), nums[0]\n",
    "        #     gap = max(1, b-a)\n",
    "        #     if gap >= k:\n",
    "        #         heappush(nums, a+k)\n",
    "        #         break \n",
    "        #     else:\n",
    "        #         heappush(nums, a+gap)\n",
    "        #         k -= gap\n",
    "        # res = 1 \n",
    "        # for num in nums:\n",
    "        #     res *= num \n",
    "        # return res % (10**9+7)\n",
    "\n",
    "        # -------------------------------------\n",
    "        MOD = 10**9 + 7\n",
    "        heapify(nums)\n",
    "        for _ in range(k):\n",
    "            num = heappop(nums)\n",
    "            heappush(nums, num+1)\n",
    "        res = 1 \n",
    "        for num in nums:\n",
    "            res *= num \n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return (nums[0] + k) % kmod\n",
    "\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        while k:\n",
    "            num = heapq.heappop(nums)\n",
    "            v = min(k, nums[0] - num)\n",
    "            v = max(v, 1)\n",
    "            k -= v\n",
    "            heapq.heappush(nums, num + v)\n",
    "\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans *= num\n",
    "            ans %= kmod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)   # 建立最小堆\n",
    "        while k:\n",
    "            k -= 1\n",
    "            # 每次操作：弹出最小值，增加 1 并重新添加\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, num + 1)\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        for i in range(k):\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "        ans = 1\n",
    "        for n in nums:\n",
    "            ans = ans*n%1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for x in nums:\n",
    "            ans = ans * x % (10 ** 9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        nums.append(float(\"inf\"))\n",
    "        for i in range(n):\n",
    "            tmp = (i + 1) * (nums[i + 1] - nums[i])\n",
    "            if k >= tmp:\n",
    "                k -= tmp\n",
    "                continue\n",
    "            d = k // (i + 1)\n",
    "            m = k % (i + 1)\n",
    "            for j in range(i + 1):\n",
    "                nums[j] = nums[i] + d\n",
    "                if j < m:\n",
    "                    nums[j] += 1\n",
    "            break\n",
    "        nums.pop()\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort()\n",
    "        # n = len(nums)\n",
    "        # while k > 0:\n",
    "        #     if nums[0] != nums[1]:\n",
    "        #         t = min(nums[1] - nums[0] + 1, k)\n",
    "        #     else:\n",
    "        #         t = 1\n",
    "        #     nums[0] += t\n",
    "        #     k -= t\n",
    "        #     nums.sort()\n",
    "        # # print(nums)\n",
    "        # return reduce(lambda x, y: x * y, nums) % (10**9+7)\n",
    "\n",
    "        # 上面为用list实现的，下面参考题解用heapq优化\n",
    "        n = len(nums)\n",
    "        heapq.heapify(nums)\n",
    "        while k:  # 等价 while k > 0\n",
    "            a = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, a+1)\n",
    "            k -= 1\n",
    "        res = 1\n",
    "        mod = 10**9+7\n",
    "        for ele in nums:\n",
    "            res *= ele\n",
    "            res %= mod\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        while k:\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, num + 1)\n",
    "            k -= 1\n",
    "\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans *= num\n",
    "            ans %= kmod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        heapify(nums)\n",
    "        ans=1\n",
    "        while k>0:\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "            k-=1\n",
    "        for x in nums:\n",
    "            ans= ans*x%mod\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)   # 建立最小堆\n",
    "        while k:\n",
    "            k -= 1\n",
    "            # 每次操作：弹出最小值，增加 1 并重新添加\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, num + 1)\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        end = 1\n",
    "        giao = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        for i in range(k):\n",
    "            num = heapq.heappop(nums)\n",
    "            heapq.heappush(nums,num + 1)\n",
    "        for i in nums:\n",
    "            end *= i\n",
    "            end %= giao\n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # 最小堆，每次将最小的加1\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        for i in range(k):\n",
    "            nums[0] = nums[0] + 1\n",
    "            heapreplace(nums, nums[0])\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # nums.sort()\n",
    "        # n = len(nums)\n",
    "        # while k > 0:\n",
    "        #     if nums[0] != nums[1]:\n",
    "        #         t = min(nums[1] - nums[0] + 1, k)\n",
    "        #     else:\n",
    "        #         t = 1\n",
    "        #     nums[0] += t\n",
    "        #     k -= t\n",
    "        #     nums.sort()\n",
    "        # mod = 10**9+7\n",
    "        # return reduce(lambda x, y: x * y % mod, nums)\n",
    "\n",
    "        # 上面为用list实现的，下面参考题解用heapq优化\n",
    "        n = len(nums)\n",
    "        heapq.heapify(nums)\n",
    "        while k:  # 等价 while k > 0\n",
    "            a = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, a+1)\n",
    "            k -= 1\n",
    "        res = 1\n",
    "        mod = 10**9+7\n",
    "\n",
    "        # 1 所有元素乘完在mod, 会超时; 2 用reduce方法替代下面for循环,性能略差 \n",
    "        # for ele in nums:\n",
    "        #     res *= ele\n",
    "        #     res %= mod\n",
    "        # return res\n",
    "        return reduce(lambda x, y: x * y % mod, nums)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:  return nums[0] + k\n",
    "        \n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        preSum = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if k >= i * nums[i] - preSum:\n",
    "                preSum += nums[i]\n",
    "            else:\n",
    "                increase = (k + preSum - i * nums[i-1]) // i\n",
    "                cnt = (k + preSum - i * nums[i-1]) % i\n",
    "                ans = (nums[i-1] + increase + 1) ** cnt * (nums[i-1] + increase) ** (i-cnt) % MOD\n",
    "                for j in range(i, n):\n",
    "                    ans = (ans * nums[j]) % MOD\n",
    "                return ans\n",
    "        \n",
    "        k -= nums[-1] * n - preSum\n",
    "        increase = k // n\n",
    "        cnt = k % n\n",
    "        ans = (nums[-1] + increase + 1) ** cnt * (nums[-1] + increase) ** (n-cnt) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        heapify(nums)\n",
    "        ans=1\n",
    "        while k>0:\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "            k-=1\n",
    "        for i in range(len(nums)):\n",
    "            ans= ans*nums[i]%mod\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        count = len(nums)\n",
    "        remain = k\n",
    "\n",
    "        dp = [0] * count\n",
    "        cap = 0\n",
    "        flag_break = False\n",
    "        \n",
    "        for i in range(1, count):\n",
    "            dp[i] = dp[i-1] + (nums[i] - nums[i-1]) * i\n",
    "            if dp[i] > k:\n",
    "                cap = i-1\n",
    "                remain = k - dp[i-1]\n",
    "                flag_break = True\n",
    "                break\n",
    "        \n",
    "        if not flag_break:\n",
    "            cap = count-1\n",
    "            remain = k - dp[cap]\n",
    "        \n",
    "        d, m = divmod(remain, cap+1)\n",
    "\n",
    "        res = 1\n",
    "\n",
    "        for _ in range(m):\n",
    "            res *= nums[cap] + d + 1\n",
    "            res %= 1000000007\n",
    "\n",
    "        for _ in range(m, cap+1):\n",
    "            res *= nums[cap] + d\n",
    "            res %= 1000000007\n",
    "\n",
    "        for ind in range(cap+1, count):\n",
    "            res *= nums[ind]\n",
    "            res %= 1000000007\n",
    "\n",
    "        return res \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            k -= 1\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = (ans * x) % (10 ** 9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % MOD\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        def mull(x, y):\n",
    "            return x * y % MOD\n",
    "\n",
    "        heapify(nums)\n",
    "\n",
    "        while k:\n",
    "            heapreplace(nums, (nums[0] + 1))\n",
    "            k -= 1\n",
    "        \n",
    "        return reduce(mull, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        nums.append(inf)\n",
    "        n = len(nums)\n",
    "        # ans = 0\n",
    "        # print(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(n - 1):\n",
    "            if (nums[i + 1] - nums[i]) * (i + 1) >= k:\n",
    "                d = k // (i + 1)\n",
    "                r = k % (i + 1)\n",
    "                # print(i, d, r)\n",
    "                tmp = (pow(nums[i] + d, i + 1 - r, mod) * pow(nums[i] + d + 1, r, mod)) % mod\n",
    "                # print(tmp)\n",
    "                for j in range(i + 1, n - 1):\n",
    "                    tmp = (tmp * nums[j]) % mod\n",
    "                return tmp\n",
    "            k -= (nums[i + 1] - nums[i]) * (i + 1)\n",
    "            # print(i, k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = (ans * num )% MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # for i in range(len(nums)):\n",
    "        #     nums[i] *= -1\n",
    "        out = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        for i in nums:\n",
    "            out = out * i % mod\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while(k>0):\n",
    "            k-=1\n",
    "            ass=heapq.heappop(nums)\n",
    "            heapq.heappush(nums,ass+1)\n",
    "        ss=1\n",
    "        for i in nums:\n",
    "            ss*=i\n",
    "            if ss>(pow(10,9)+7):\n",
    "                ss=ss%(pow(10,9)+7)\n",
    "        return ss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while k > 0:\n",
    "            top = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, top + 1)\n",
    "            k -= 1\n",
    "\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= 1000000007\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7  # 模数\n",
    "\n",
    "        # 初始化一个最小堆\n",
    "        heapq.heapify(nums)\n",
    "        \n",
    "        # 执行k次操作，每次都找到最小的数并加1\n",
    "        for _ in range(k):\n",
    "            smallest = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, smallest + 1)\n",
    "\n",
    "        # 计算最终的乘积\n",
    "        product = 1\n",
    "        for num in nums:\n",
    "            product = (product * num) % MOD\n",
    "\n",
    "        return product\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.maximumProduct([0, 4], 5))  # 输出应为 20\n",
    "print(sol.maximumProduct([6, 3, 3, 2], 2))  # 输出应为 216\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        M = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        s = k + nums[0]\n",
    "        m = 1\n",
    "        while m < n:\n",
    "            if s // m <= nums[m]:\n",
    "                break\n",
    "            s += nums[m]\n",
    "            m += 1\n",
    "        x = s // m\n",
    "        c = s % m\n",
    "        res = 1\n",
    "        for _ in range(m - c):\n",
    "            res = res * x % M\n",
    "        x += 1\n",
    "        for _ in range(c):\n",
    "            res = res * x % M\n",
    "        for i in range(m, n):\n",
    "            res = res * nums[i] % M\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        INT_MAX = 10**9 +7\n",
    "        ans = 1\n",
    "        while k!= 0:\n",
    "            heapreplace(nums, nums[0]+1)\n",
    "            k-= 1\n",
    "        for i in range(len(nums)):\n",
    "            ans = ans *nums[i] % INT_MAX\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while(k>0):\n",
    "            k-=1\n",
    "            heapq.heappush(nums,heapq.heappop(nums)+1)\n",
    "        ss=1\n",
    "        for i in nums:\n",
    "            ss*=i\n",
    "            if ss>(pow(10,9)+7):\n",
    "                ss=ss%(pow(10,9)+7)\n",
    "        return ss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        mod = 10**9 + 7\n",
    "        for _ in range(k):\n",
    "            heapq.heapreplace(nums, nums[0] + 1)\n",
    "        ans = 1\n",
    "        for i in nums:\n",
    "            ans = ans * i % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums,nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while k>0:\n",
    "            heapq.heapreplace(nums, nums[0]+1)\n",
    "            k -=1\n",
    "        res = 1\n",
    "        for i in nums:\n",
    "            res *=i\n",
    "            res %= 1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        res = 1\n",
    "        while k:\n",
    "            x = heappop(nums)\n",
    "            heappush(nums, x + 1)\n",
    "            k -= 1\n",
    "        for x in nums:\n",
    "            res = (res * x) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:  return nums[0] + k\n",
    "        \n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        preSum = nums[0]\n",
    "        for i in range(1, n):\n",
    "            if k >= i * nums[i] - preSum:\n",
    "                preSum += nums[i]\n",
    "            else:\n",
    "                increase = (k + preSum - i * nums[i-1]) // i\n",
    "                cnt = (k + preSum - i * nums[i-1]) % i\n",
    "                ans = (nums[i-1] + increase + 1) ** cnt * (nums[i-1] + increase) ** (i-cnt) % MOD\n",
    "                for j in range(i, n):\n",
    "                    ans = (ans * nums[j]) % MOD\n",
    "                return ans\n",
    "        \n",
    "        k -= nums[-1] * n - preSum\n",
    "        increase = k // n\n",
    "        cnt = k % n\n",
    "        ans = (nums[-1] + increase + 1) ** cnt * (nums[-1] + increase) ** (n-cnt) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        nums.append(float(\"INF\"))\n",
    "        # 遍历数组，优化模拟更新的过程\n",
    "        for i in range(n):\n",
    "            # 判断是否可以将数组下标 [0, i] 的元素更新为 nums[i+1]\n",
    "            tmp = (i + 1) * (nums[i+1] - nums[i])\n",
    "            if k >= tmp:\n",
    "                # 可以，则更新剩余的操作次数\n",
    "                k -= tmp\n",
    "                continue\n",
    "            # 不可以，则计算最终数组的元素\n",
    "            d = k // (i + 1)\n",
    "            m = k % (i + 1)\n",
    "            for j in range(i + 1):\n",
    "                nums[j] = nums[i] + d\n",
    "                if j < m:\n",
    "                    nums[j] += 1\n",
    "            break\n",
    "        nums.pop()\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # 贪心：从组最小值开始+1 == 下一个大的数\n",
    "        # 数据结构：最小堆，每次弹出最小值，加上值后放回去，再弹出最小值\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        while k > 0:\n",
    "            cur_min = heappop(nums)\n",
    "            cur_min += 1\n",
    "            heapq.heappush(nums,cur_min)\n",
    "            k -= 1\n",
    "\n",
    "        res = 1\n",
    "        mod = 10**9 + 7\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= mod\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "            k-=1\n",
    "        ans=1\n",
    "        for i in range(len(nums)):\n",
    "            ans=ans*nums[i]%mod\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        m = len(nums)\n",
    "        nums.sort()\n",
    "        dp = [0]*m\n",
    "\n",
    "        # 初始化fin rem\n",
    "        fin = m-1\n",
    "        rem = k\n",
    "\n",
    "        # 寻找能一步抹平的右边界\n",
    "        for i in range(1,m):\n",
    "            dp[i] = (nums[i]-nums[i-1]) * i + dp[i-1]\n",
    "            if dp[i] > k:\n",
    "                fin = i-1\n",
    "                rem = k - dp[fin]\n",
    "                break\n",
    "\n",
    "        # 处理溢出边界\n",
    "        if dp[m-1]!=0 and dp[m-1] <= k:\n",
    "            fin = m-1\n",
    "            rem = k - dp[m-1]\n",
    "\n",
    "        # 用k的边角料 “撒胡椒面”\n",
    "        h = nums[fin] + rem//(fin+1)\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        # 第一块\n",
    "        for i in range(rem%(fin+1)):\n",
    "            ans *= (h+1)\n",
    "            ans %= 1000000007\n",
    "        \n",
    "        # 第二块\n",
    "        for i in range(rem%(fin+1), fin+1):\n",
    "            ans *= h\n",
    "            ans %= 1000000007\n",
    "        \n",
    "        # 第三块\n",
    "        for i in range(fin+1,m):\n",
    "            ans *= nums[i]\n",
    "            ans %= 1000000007\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        cnt= 1\n",
    "        for i in range(n-1):\n",
    "            if nums[i+1]>nums[i]:\n",
    "                if cnt*(nums[i+1]-nums[i])<=k:\n",
    "                    k -= cnt*(nums[i+1]-nums[i])\n",
    "                else:\n",
    "                    break\n",
    "            cnt += 1\n",
    "        mod = 10**9+7\n",
    "        if cnt == n:\n",
    "            val = nums[-1]+k//n\n",
    "            res = pow(val+1, k%n, mod)*pow(val, n-k%n, mod)\n",
    "            return res%mod\n",
    "        else:\n",
    "            val= nums[cnt-1]+k//cnt\n",
    "            res = pow(val, cnt-k%cnt, mod)*pow(val+1, k%cnt, mod)\n",
    "            for i in range(cnt, n):\n",
    "                res = (res*nums[i])%mod\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = ans * x % (10**9 + 7)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) < 2:\n",
    "            return nums[0] + k\n",
    "        if max(nums) == min(nums):\n",
    "            n = len(nums)\n",
    "            a, b = k//n, k%n \n",
    "            # print(a, b, n)\n",
    "            res = 1\n",
    "            for i, num in enumerate(nums):\n",
    "                if i < b:\n",
    "                    res *= num + a + 1\n",
    "                else:\n",
    "                    res *= num + a\n",
    "                res = res % (10**9+7)\n",
    "            return res\n",
    "        nums_heap = heapify(nums)\n",
    "        while k:\n",
    "            a, b = heappop(nums), nums[0]\n",
    "            gap = max(1, b-a)\n",
    "            if gap >= k:\n",
    "                heappush(nums, a+k)\n",
    "                break \n",
    "            else:\n",
    "                heappush(nums, a+gap)\n",
    "                k -= gap\n",
    "        res = 1 \n",
    "        for num in nums:\n",
    "            res *= num \n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            x = heappop(nums)\n",
    "            heappush(nums, x+1)\n",
    "            k -= 1\n",
    "        \n",
    "        return reduce(lambda x, y:x*y % mod, nums) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "贪心策略，每次都给最小的数增加1\n",
    "'''\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        for _ in range(k):\n",
    "            tmp = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, tmp+1)\n",
    "        res = 1\n",
    "        for num in nums:\n",
    "            res *= num\n",
    "            res %= 10**9+7\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        n = len(nums)\n",
    "        ans = 1\n",
    "        for i in range(k):\n",
    "            heapq.heappush(nums, heapq.heappop(nums) + 1)\n",
    "        for i in range(n):\n",
    "            ans *= nums[i]\n",
    "            ans %= MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while k:\n",
    "            a=heapq.heappop(nums)\n",
    "            heapq.heappush(nums,a+1)\n",
    "            k-=1\n",
    "        ans=1\n",
    "        for num in nums:\n",
    "            ans=(ans*num)%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        while(k>0):\n",
    "            k-=1\n",
    "            ass=heapq.heappop(nums)\n",
    "            heapq.heappush(nums,ass+1)\n",
    "        ss=1\n",
    "        for i in nums:\n",
    "            ss*=i\n",
    "            if ss>(pow(10,9)+7):\n",
    "                ss=ss%(pow(10,9)+7)\n",
    "        return ss\n",
    "    \n",
    "54\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        heapq.heapify(nums)\n",
    "        while k:\n",
    "            k -= 1\n",
    "            cur = heapq.heappop(nums)\n",
    "            heapq.heappush(nums, cur + 1)\n",
    "        \n",
    "        ans = 1\n",
    "        for ch in nums:\n",
    "            ans *= ch\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0] + k\n",
    "        # 每次选择最小的数增加，至少增加1，最多增加与第二小的数的差值或k\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            small = heappop(nums)\n",
    "            increase = min(nums[0] - small + 1, k)\n",
    "            k -= increase\n",
    "            heappush(nums, small + increase)\n",
    "        \n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = ans * x % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        while k:\n",
    "            heapreplace(nums, nums[0] + 1)\n",
    "            k -= 1\n",
    "\n",
    "        ans = 1\n",
    "\n",
    "        for x in nums:\n",
    "            print(x)\n",
    "            ans = ans * x % (10 ** 9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        while k> 0 :\n",
    "            k -= 1\n",
    "            num = heapq.heappop(nums)\n",
    "            num += 1\n",
    "            \n",
    "            heapq.heappush(nums, num)\n",
    "        ans = 1 \n",
    "        while nums:\n",
    "            ans*= heapq.heappop(nums)\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        heapify(nums)\n",
    "        for _ in range(k):\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "        cnt=Counter(nums)\n",
    "        res = 1 \n",
    "        for k,v in cnt.items():\n",
    "            res *= pow(k,v,MOD)\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        heapify(nums)\n",
    "        for _ in range(k):\n",
    "            heapreplace(nums,nums[0]+1)\n",
    "        cnt=Counter(nums)\n",
    "        res = 1 \n",
    "        for k,v in cnt.items():\n",
    "            res *= k**v\n",
    "            res %= MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        h=[]\n",
    "        ans=1\n",
    "        for i in nums:\n",
    "            heapq.heappush(h,i)\n",
    "        for i in range(k):\n",
    "            x=heapq.heappop(h)\n",
    "            heapq.heappush(h,x+1)\n",
    "        for i in h:\n",
    "            ans*=i \n",
    "            ans%=(10**9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        for num in nums:\n",
    "            heapq.heappush(q, num)\n",
    "        while k:\n",
    "            cur = heapq.heappop(q)\n",
    "            heapq.heappush(q, cur + 1)\n",
    "            k -= 1\n",
    "        res = 1\n",
    "        for i in range(len(q)):\n",
    "            res *= q[i]\n",
    "            res %= int(1e9 + 7)\n",
    "        return res                                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        # 将k次操作的每次操作都分给nums中最小的数，这样每次增加的乘积值为最大贪心\n",
    "        from heapq import heapify,heappush,heappop\n",
    "        pq=[x for x in nums]\n",
    "        heapify(pq)\n",
    "        for _ in range(k):\n",
    "            x=heappop(pq)\n",
    "            heappush(pq,x+1)\n",
    "        Mod=10**9+7\n",
    "        ans=1\n",
    "        for x in pq:\n",
    "            ans=ans*x%Mod\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        for num in nums:\n",
    "            heapq.heappush(q, num)\n",
    "        while k:\n",
    "            cur = heapq.heappop(q)\n",
    "            target = cur + k\n",
    "            if q and q[0] < target:\n",
    "                target = q[0] + 1\n",
    "            heapq.heappush(q, target)\n",
    "            k -= target - cur\n",
    "        res = 1\n",
    "        for i in range(len(q)):\n",
    "            res *= q[i]\n",
    "            res %= int(1e9 + 7)\n",
    "        return res                                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        que = queue.PriorityQueue()\n",
    "\n",
    "        for num in nums:\n",
    "            que.put(num)\n",
    "\n",
    "        while k > 0:\n",
    "            num = que.get()\n",
    "            que.put(num + 1)\n",
    "            k -= 1\n",
    "        \n",
    "        ans = 1 \n",
    "        \n",
    "        while not que.empty():\n",
    "            num = que.get()\n",
    "            ans *= num \n",
    "            ans %= int(1e9 + 7)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        l = len(nums)\n",
    "        h = []\n",
    "        for i in range(l):\n",
    "            heappush(h, nums[i])\n",
    "        for i in range(k):\n",
    "            tmp = heappop(h)\n",
    "            tmp += 1\n",
    "            heappush(h, tmp)\n",
    "        res = 1\n",
    "        for i in range(l):\n",
    "            res = (res*h[i]) % (1e9+7)\n",
    "        return int(res)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0] + k\n",
    "        Q = []\n",
    "        for x in nums:\n",
    "            heappush(Q, x)\n",
    "        while k > 0:\n",
    "            t = heappop(Q)\n",
    "            t += 1\n",
    "            heappush(Q, t)\n",
    "            k -= 1\n",
    "        ans = 1\n",
    "        while Q:\n",
    "            ans = (ans * heappop(Q)) % (10 ** 9 + 7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        for _ in range(k):\n",
    "            t = nums[0]\n",
    "            nums.pop(0)\n",
    "            nums.add(t + 1)\n",
    "        ans = 1\n",
    "        for x in nums:\n",
    "            ans = ans * x % 1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        nums = SortedList(nums)\n",
    "        for i in range(k):\n",
    "            first = nums.pop(0)\n",
    "            nums.add(first + 1)\n",
    "        ans = 1\n",
    "        for num in nums:\n",
    "            ans = ans * num % (10 ** 9 + 7)\n",
    "        return ans\n",
    "        # return math.prod(nums) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        cnt_dict = {}\n",
    "        for num in nums:\n",
    "            cnt_dict[num] = cnt_dict.get(num, 0) + 1\n",
    "        sorted_cnt = sorted(cnt_dict.items(), key=lambda d:d[0])\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        now = sorted_cnt[0][1]\n",
    "        for index in range(1, len(sorted_cnt)):\n",
    "            diff = sorted_cnt[index][0] - sorted_cnt[index - 1][0]\n",
    "            if diff * now <= k:\n",
    "                k -= diff * now\n",
    "                now += sorted_cnt[index][1]\n",
    "            else:\n",
    "                res = 1\n",
    "                for num, cnt in sorted_cnt[index:]:\n",
    "                    for _ in range(cnt):\n",
    "                        res = res * num % mod\n",
    "                \n",
    "                delta = k // now\n",
    "                k %= now\n",
    "                for _ in range(k):\n",
    "                    res = res * (sorted_cnt[index - 1][0] + delta + 1) % mod\n",
    "                for _ in range(k, now):\n",
    "                    res = res * (sorted_cnt[index - 1][0] + delta) % mod\n",
    "                \n",
    "                return res\n",
    "\n",
    "        res = 1\n",
    "        delta = k // now\n",
    "        k %= now\n",
    "        for _ in range(k):\n",
    "            res = res * (sorted_cnt[-1][0] + delta + 1) % mod\n",
    "        for _ in range(k, now):\n",
    "            res = res * (sorted_cnt[-1][0] + delta) % mod\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int], k: int) -> int:\n",
    "        ##每次对最小元素增加1\n",
    "        MOD=10**9+7\n",
    "        h=[[k,v] for k,v in Counter(nums).items()]\n",
    "        heapify(h)\n",
    "        while k>=h[0][1]:\n",
    "            theMin,count=heappop(h)\n",
    "            if h:\n",
    "                if h[0][0]==theMin+1:\n",
    "                    h[0][1]+=count\n",
    "                else:\n",
    "                    heappush(h,[theMin+1,count])\n",
    "                k-=count\n",
    "            else:\n",
    "                heappush(h,[theMin+k//count,count])\n",
    "                k%=count\n",
    "            # print(h,k)\n",
    "        ##此时对于h[i][0]，其中只能有k个加一\n",
    "        res=1\n",
    "        res=res*pow(h[0][0]+1,k,MOD)\n",
    "        res=res*pow(h[0][0],h[0][1]-k,MOD)\n",
    "        for j in range(1,len(h)):\n",
    "            res=res*pow(h[j][0],h[j][1],MOD)%MOD\n",
    "        return res%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        a = nums[-1] * nums[-2] * nums[-3]\n",
    "        b = nums[0] * nums[1] * nums[-1]\n",
    "        return max(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[-1]*nums[-2]*nums[-3],nums[-1]*nums[0]*nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[-1]*nums[-2]*nums[-3],nums[-1]*nums[0]*nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        a = nums[n-3] * nums[n-2] * nums[n-1]\n",
    "        b = nums[0] * nums[1] * nums[n-1]\n",
    "        c = nums[n-4] * nums[n-3] * nums[n-2] if n >= 4 else -inf\n",
    "\n",
    "        return max(a, b, c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "from operator import mul\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return max(reduce(mul, nums[:3]), reduce(mul, [nums[-1]]+nums[:2]), reduce(mul, nums[-2:]+[nums[0]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        count_ne = 0\n",
    "        count_ze = 0\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                count_ne += 1\n",
    "            if num == 0:\n",
    "                count_ze += 1\n",
    "        if count_ne + count_ze == len(nums):\n",
    "            if count_ze > 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return nums[-1]*nums[-2]*nums[-3]\n",
    "        dp = [[0 for _ in range(3)] for _ in range(len(nums))]\n",
    "        for j in range(3):\n",
    "            dp[0][j] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i][0] = max(dp[i-1][0], nums[i])\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(1,3):\n",
    "                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] * nums[i])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = nums[-1] * nums[-2] * nums[-3]\n",
    "        b = nums[0] * nums[1] * nums[-1]\n",
    "        return max(a, b)\n",
    "\n",
    "\n",
    "        '''temp = 1\n",
    "        if(len(nums)<=3):\n",
    "            for i in nums:\n",
    "                temp = temp * i\n",
    "        else:\n",
    "            nums = sorted(nums,reverse=True)\n",
    "            if(nums[-1] > 0):\n",
    "                for i in nums:\n",
    "                    temp *= i\n",
    "            else:\n",
    "                if(nums[2] < 0):\n",
    "                    nums = nums.sort()\n",
    "                    temp =  nums[0] * nums[1] * nums[-1]\n",
    "                else:\n",
    "                    temp =  nums[0] * nums[1] * nums[2]\n",
    "        return temp\n",
    "        \n",
    "'''\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        num_0 = nums[0]\n",
    "        num_1 = nums[1]\n",
    "        num_2 = nums[2]\n",
    "        num_re1 = nums[-1]\n",
    "        num_re2 = nums[-2]\n",
    "        num_re3 = nums[-3]\n",
    "        # return max(nums[0]*nums[1]*nums[2], nums[0]*nums[1]*nums[-1], nums[-3]*nums[-2]*nums[-1])\n",
    "        return max(num_0*num_1*num_2, num_0*num_1*num_re1,num_re1*num_re2*num_re3)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        \"\"\"排序方法，时间复杂度O(nlog(n))\"\"\"\n",
    "        # nums.sort()\n",
    "        # return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])\n",
    "\n",
    "        \"\"\"遍历一遍数组，不使用排序，时间复杂度O(n)\"\"\"\n",
    "        max1 = -float('inf')       # 第一大的值\n",
    "        max2 = -float('inf')       # 第二大的值\n",
    "        max3 = -float('inf')       # 第三大的值\n",
    "        min1 = float('inf')        # 第一小的值\n",
    "        min2 = float('inf')        # 第二小的值\n",
    "\n",
    "        for num in nums:\n",
    "            if num > max1:       \n",
    "                max3 = max2        \n",
    "                max2 = max1       \n",
    "                max1 = num        \n",
    "            elif num > max2:       \n",
    "                max3 = max2       \n",
    "                max2 = num         \n",
    "            elif num > max3:      \n",
    "                max3 = num        \n",
    "            \n",
    "            if num < min1:        \n",
    "                min2 = min1       \n",
    "                min1 = num        \n",
    "            elif num < min2:       \n",
    "                min2 = num        \n",
    "            \n",
    "        return max(max1 * max2 * max3, max1 * min1 * min2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: list[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return\n",
    "        nums.sort(reverse=True)\n",
    "        if nums[-2] < 0:\n",
    "            return max(nums[0] * nums[1] * nums[2], nums[0] * nums[-1] * nums[-2])\n",
    "        return nums[0] * nums[1] * nums[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=False)\n",
    "        max=-10**10\n",
    "        left=0\n",
    "        a=nums[len(nums)-1]\n",
    "        for left in range(len(nums)-2):\n",
    "            sum=a\n",
    "            sum*=nums[left]*nums[left+1]\n",
    "            if sum>max:\n",
    "                max=sum\n",
    "        return max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        a,b,c=float('-inf'),float('-inf'),float('-inf')           #a>=b>=c\n",
    "        d,e=float('inf'),float('inf')         #d<=e\n",
    "        for i in nums:\n",
    "            if i>=a:\n",
    "                a,b,c=i,a,b\n",
    "            elif a>i>=b:\n",
    "                b,c=i,b\n",
    "            elif b>i>=c:\n",
    "                c=i\n",
    "            if i<=d:\n",
    "                d,e=i,d\n",
    "            elif d<i<=e:\n",
    "                e=i\n",
    "        value=max(a*b*c,a*d*e)\n",
    "        return value\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans1 = nums[-1] * nums[-2] * nums[-3]\n",
    "        ans2 = nums[0] * nums[1] * nums[-1]\n",
    "        ans = ans1 if ans1 > ans2 else ans2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if nums[0]>=0 or nums[len(nums)-1]<=0: \n",
    "            return nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3]\n",
    "        return max(nums[0]*nums[1]*nums[len(nums)-1],nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return max(nums[0] * nums[1] * nums[2], nums[0] * nums[-1] * nums[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        r=max(nums[0]*nums[1]*nums[2],nums[0]*nums[-1]*nums[-2])\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = nums[-1] * nums[-2] * nums[-3]\n",
    "        b = nums[0] * nums[1] * nums[-1]\n",
    "        return max(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = nums[0]*nums[1]*nums[-1]\n",
    "        b = nums[-1]*nums[-2]*nums[-3]\n",
    "        return max(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=sorted(nums)\n",
    "        a=nums[n-1]*nums[n-2]*nums[n-3]\n",
    "        b=nums[0]*nums[1]*nums[2]\n",
    "        if n==3:\n",
    "            return a\n",
    "        else:\n",
    "            x=nums[0]*nums[1]*nums[n-1]\n",
    "            y=nums[0]*nums[n-2]*nums[n-1]  \n",
    "            return max(x,y,a,b)       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:   \n",
    "        nums.sort(reverse=True)\n",
    "        a = nums[0] * nums[1] * nums[2] #全是正数/负数 情况下的最大\n",
    "        b = nums[0] * nums[-1] * nums[-2]\n",
    "        return max(a,b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        a = nums[n-3] * nums[n-2] * nums[n-1]\n",
    "        b = nums[0] * nums[1] * nums[n-1]\n",
    "\n",
    "        return max(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = nums[-1] * nums[-2] * nums[-3]\n",
    "        b = nums[0] * nums[1] * nums[-1]\n",
    "        return max(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        li = sorted(nums,reverse=False)\n",
    "        return max(li[0]*li[1]*li[-1],li[-1]*li[-2]*li[-3])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return max(nums[0]*nums[1]*nums[n-1] , nums[n-3]*nums[n-2]*nums[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        # 从大到小排序\n",
    "        nums.sort(reverse=True)\n",
    "        fu = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0:\n",
    "                fu += 1\n",
    "\n",
    "        # 如果全部都是正数或者负数就直接最大数相乘\n",
    "        if fu == 0 or fu == len(nums) or fu == 1:\n",
    "            return nums[0] * nums[1] * nums[2]\n",
    "        \n",
    "        # 如果有两个及以上个负数\n",
    "        else:\n",
    "            # 三个正数\n",
    "            num1 = nums[0] * nums[1] * nums[2]\n",
    "            # 二负一正\n",
    "            num2 = nums[0] * nums[len(nums)-1] * nums[len(nums)-2]\n",
    "            \n",
    "            max_num = max(num1, num2)\n",
    "            return max_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        max1, max2, max3, min1, min2, = -9999, -9999, -9999, 9999, 9999\n",
    "        for num in nums:\n",
    "            if num > max1:\n",
    "                max3 = max2\n",
    "                max2 = max1\n",
    "                max1 = num\n",
    "            elif num > max2:\n",
    "                max3 = max2\n",
    "                max2 = num\n",
    "            elif num > max3:\n",
    "                max3 = num\n",
    "            \n",
    "            if num < min1:\n",
    "                min2 = min1\n",
    "                min1 = num\n",
    "            elif num < min2:\n",
    "                min2 = num\n",
    "        return max(max1 * max2 * max3, min1 * min2 * max1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        ans = nums[len(nums) - 1] * nums[len(nums) - 2] * nums[len(nums) - 3]\n",
    "        if nums[0] < 0:\n",
    "            if nums[1] < 0:\n",
    "                ans = max(ans, nums[0] * nums[1] * nums[len(nums) - 1])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        a = nums[-1] * nums[-2] * nums[-3]\n",
    "        b = nums[0] * nums[1] * nums[-1]\n",
    "        return max(a, b)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==3:\n",
    "            return nums[0]*nums[1]*nums[2]\n",
    "\n",
    "        nums.sort()\n",
    "        return max(nums[0]*nums[1]*nums[n-1],nums[n-3]*nums[n-2]*nums[n-1])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[-1]*nums[-2]*nums[-3], nums[-1]*nums[0]*nums[1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return max(nums[0]*nums[1]*nums[2],nums[0]*nums[-1]*nums[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*max(nums[2::]))\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        m1 = nums[-1] * nums[-2] * nums[-3]\n",
    "        m2 = nums[-1] * nums[0] * nums[1]\n",
    "        return max(m1, m2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*nums[-1])\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self,nums):\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        if N<5 and nums[1]==0:\n",
    "            return 0\n",
    "        else:      \n",
    "            a = nums[-1] * nums[-2] * nums[-3]\n",
    "            b = nums[0] * nums[1] * nums[-1]\n",
    "            return max(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[-1]*nums[-2]*nums[-3],nums[0]*nums[1]*nums[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        min1, min2 = float('inf'), float('inf')\n",
    "        max1, max2, max3 = float('-inf'), float('-inf'), float('-inf')\n",
    "        for x in nums:\n",
    "            if x < min1:\n",
    "                min2, min1 = min1, x\n",
    "            elif x < min2:\n",
    "                min2 = x\n",
    "            if x > max1:\n",
    "                max3, max2, max1 = max2, max1, x\n",
    "            elif x > max2:\n",
    "                max3, max2 = max2, x\n",
    "            elif x >max3:\n",
    "                max3 = x\n",
    "        return max(min1*min2*max1, max1*max2*max3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=sorted(nums)\n",
    "        a=nums[n-1]*nums[n-2]*nums[n-3]\n",
    "        b=nums[0]*nums[1]*nums[2]\n",
    "        x=nums[0]*nums[1]*nums[n-1]\n",
    "        y=nums[0]*nums[n-2]*nums[n-1]\n",
    "        if n==3:\n",
    "            return a\n",
    "        else:  \n",
    "            return max(x,y,a,b)       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return max(nums[0]*nums[1]*nums[n-1], nums[n-1]*nums[n-2]*nums[n-3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        v1 = nums[-1] * nums[-2] * nums[-3]\n",
    "        v2 = nums[0] * nums[1] * nums[-1]\n",
    "\n",
    "        return max(v1, v2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=False)\n",
    "        n=len(nums)\n",
    "        return max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        n = sorted(nums)\n",
    "        return max(n[-1]*n[-2]*n[-3], n[0]*n[1]*n[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[len(nums) - 1] * nums[len(nums) - 2] * nums[len(nums) - 3]\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            ans = max(ans, nums[0] * nums[1] * nums[len(nums) - 1])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*max(nums[2::]))\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: list[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return\n",
    "        nums.sort(reverse=True)\n",
    "        if nums[-2] < 0:\n",
    "            return max(nums[0] * nums[1] * nums[2], nums[0] * nums[-1] * nums[-2])\n",
    "        return nums[0] * nums[1] * nums[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=sorted(nums)\n",
    "        a=nums[n-1]*nums[n-2]*nums[n-3]\n",
    "        b=nums[0]*nums[1]*nums[2]\n",
    "        if n==3:\n",
    "            return a\n",
    "        else:\n",
    "            x=nums[0]*nums[1]*nums[n-1]\n",
    "            y=nums[0]*nums[n-2]*nums[n-1]  \n",
    "            return max(x,y,a,b)       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*nums[-1])\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self,nums):\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        if N<5 and nums[1]==0:\n",
    "            return 0         \n",
    "        else:      \n",
    "            a = nums[-1] * nums[-2] * nums[-3]\n",
    "            b = nums[0] * nums[1] * nums[-1]\n",
    "            return max(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        result1 = result2 = 1\n",
    "        nums.sort(reverse=True)\n",
    "        result1 *= nums[0]* nums[1] * nums[2]\n",
    "        result2 = nums[-1] * nums[-2] * nums[0]\n",
    "        return max(result1,result2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        \"\"\"排序方法，时间复杂度O(nlog(n))\"\"\"\n",
    "        # nums.sort()\n",
    "        # return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])\n",
    "\n",
    "        \"\"\"遍历一遍数组，不使用排序，时间复杂度O(n)\"\"\"\n",
    "        max1 = -float('inf')       # 第一大的值\n",
    "        max2 = -float('inf')       # 第二大的值\n",
    "        max3 = -float('inf')       # 第三大的值\n",
    "        min1 = float('inf')        # 第一小的值\n",
    "        min2 = float('inf')        # 第二小的值\n",
    "\n",
    "        for num in nums:\n",
    "            if num > max1:         # 啥？你比第一大的值还大？？那好吧，你去做老大\n",
    "                max3 = max2        # 原老二委屈一下你，去做老三吧，难受...\n",
    "                max2 = max1        # 原老大委屈一下你，去做老二吧，很难受...\n",
    "                max1 = num         # 大哥快请上座！！！\n",
    "            elif num > max2:       # 嗯？你比第二大的值大啊？？那行吧，老二给你做，别碰老大啊，他脾气不好...\n",
    "                max3 = max2        # 原老二委屈一下你，去做老三吧，难受...\n",
    "                max2 = num         # 二哥请上座！！\n",
    "            elif num > max3:       # 别舞舞喳喳的，不就比第三大的值大么？？去去去，那个位置给你了...\n",
    "                max3 = num         # 三哥上座！\n",
    "            \n",
    "            if num < min1:         # 啊？你比第一小的值还小，哈哈哈，笑死我了，来来来，快去！\n",
    "                min2 = min1        # 原第一小，恭喜你，终于找到比你小的了，你现在是第二小！\n",
    "                min1 = num         # 老实呆着，你现在是最小的了！！！\n",
    "            elif num < min2:       # 哦？你比第二小的值小？比最小的还大，嗯..那你去做第二小\n",
    "                min2 = num         # 来吧，你现在是第二小，原第二小解脱了！\n",
    "            \n",
    "        return max(max1 * max2 * max3, max1 * min1 * min2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        x,y = nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1]\n",
    "        return max(x, y)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        \n",
    "\n",
    "        nums.sort()\n",
    "        a = nums[-1] * nums[-2] * nums[-3]\n",
    "        b = nums[0] * nums[1] * nums[-1]\n",
    "        return max(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*nums[-1])\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "            nums.sort()  # 对数组进行排序  \n",
    "            return max(nums[-1] * nums[-2] * nums[-3], nums[0] * nums[1] * nums[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        max1 = -float('inf')       # 第一大的值\n",
    "        max2 = -float('inf')       # 第二大的值\n",
    "        max3 = -float('inf')       # 第三大的值\n",
    "        min1 = float('inf')        # 第一小的值\n",
    "        min2 = float('inf')        # 第二小的值\n",
    "\n",
    "        for num in nums:\n",
    "            if num > max1:         # 啥？你比第一大的值还大？？那好吧，你去做老大\n",
    "                max3 = max2        # 原老二委屈一下你，去做老三吧，难受...\n",
    "                max2 = max1        # 原老大委屈一下你，去做老二吧，很难受...\n",
    "                max1 = num         # 大哥快请上座！！！\n",
    "            elif num > max2:       # 嗯？你比第二大的值大啊？？那行吧，老二给你做，别碰老大啊，他脾气不好...\n",
    "                max3 = max2        # 原老二委屈一下你，去做老三吧，难受...\n",
    "                max2 = num         # 二哥请上座！！\n",
    "            elif num > max3:       # 别舞舞喳喳的，不就比第三大的值大么？？去去去，那个位置给你了...\n",
    "                max3 = num         # 三哥上座！\n",
    "            \n",
    "            if num < min1:         # 啊？你比第一小的值还小，哈哈哈，笑死我了，来来来，快去！\n",
    "                min2 = min1        # 原第一小，恭喜你，终于找到比你小的了，你现在是第二小！\n",
    "                min1 = num         # 老实呆着，你现在是最小的了！！！\n",
    "            elif num < min2:       # 哦？你比第二小的值小？比最小的还大，嗯..那你去做第二小\n",
    "                min2 = num         # 来吧，你现在是第二小，原第二小解脱了！\n",
    "            \n",
    "        return max(max1 * max2 * max3, max1 * min1 * min2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: list[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return\n",
    "        nums.sort(reverse=True)\n",
    "        if nums[-2] < 0:\n",
    "            return max(nums[0] * nums[1] * nums[2], nums[0] * nums[-1] * nums[-2])\n",
    "        return nums[0] * nums[1] * nums[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[0] * nums[1] * nums[-1], nums[-1] * nums[-2] * nums[-3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        multi = 0\n",
    "        if nums[0]*nums[1]*nums[len(nums)-1] > nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3]:\n",
    "            multi = nums[0]*nums[1]*nums[len(nums)-1]\n",
    "        else:\n",
    "            multi = nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3]\n",
    "        return multi        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=sorted(nums)\n",
    "        a=nums[n-1]*nums[n-2]*nums[n-3]\n",
    "        b=nums[0]*nums[1]*nums[2]\n",
    "        if n==3:\n",
    "            return a\n",
    "        if (nums[n-1]<0)or(nums[0]>0):\n",
    "            return a\n",
    "        else:\n",
    "            x=nums[0]*nums[1]*nums[n-1]\n",
    "            y=nums[0]*nums[n-2]*nums[n-1]  \n",
    "            return max(x,y,a,b)       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*max(nums[2::]))\n",
    "        else:\n",
    "            return nums[-1] * nums[-2] * nums[-3]\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*max(nums[2::]))\n",
    "        else:\n",
    "            return nums[-1] * nums[-2] * nums[-3]\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*nums[-1])\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "\n",
    "        max1 = float(\"-inf\")\n",
    "        max2 = float(\"-inf\")\n",
    "        max3 = float(\"-inf\")\n",
    "        min1 = float(\"inf\")\n",
    "        min2 = float(\"inf\")\n",
    "\n",
    "        for num in nums:\n",
    "            if num > max1:\n",
    "                max3 = max2\n",
    "                max2 = max1\n",
    "                max1 = num\n",
    "            elif num > max2:\n",
    "                max3 = max2\n",
    "                max2 = num\n",
    "            elif num > max3:\n",
    "                max3 = num\n",
    "\n",
    "\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "            if num < min1:\n",
    "                min2 = min1\n",
    "                min1 = num\n",
    "            elif num < min2:\n",
    "                min2 = num\n",
    "\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "        return max(max1*max2*max3, max1*min1*min2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        low,mid,high = -inf,-inf,-inf\n",
    "        nums.sort()\n",
    "        if nums[0] < 0 and nums[1] < 0:\n",
    "            res.append(nums[0]*nums[1]*max(nums[2::]))\n",
    "        else:\n",
    "            return nums[-1] * nums[-2] * nums[-3]\n",
    "        for i in nums:\n",
    "            if i > high:\n",
    "                low,mid,high = mid,high,i\n",
    "            elif i > mid:\n",
    "                low,mid = mid,i\n",
    "            elif i > low:\n",
    "                low = i\n",
    "        res.append(low*mid*high)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        a = b = c = float('-inf')\n",
    "        d = e = float('inf')\n",
    "        for num in nums:\n",
    "            # 更新最大三个数\n",
    "            if num > a:\n",
    "                a, b, c = num, a, b\n",
    "            elif num > b:\n",
    "                b, c = num, b\n",
    "            elif num > c:\n",
    "                c = num\n",
    "            # 更新最小两个数\n",
    "            if num < d:\n",
    "                d, e = num, d\n",
    "            elif num < e:\n",
    "                e = num\n",
    "\n",
    "        return max(d * e * a, a * b * c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: list[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return\n",
    "        nums.sort(reverse=True)\n",
    "        if nums[-2] < 0:\n",
    "            return max(nums[0] * nums[1] * nums[2], nums[0] * nums[-1] * nums[-2])\n",
    "        return nums[0] * nums[1] * nums[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: list[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return\n",
    "        nums.sort(reverse=True)\n",
    "        return nums[0] * nums[1] * nums[2] if nums[0] * nums[1] * nums[2] > nums[0] * nums[-1] * nums[-2] else nums[0] * nums[-1] * nums[-2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        max1 = -float('inf')   \n",
    "        max2 = -float('inf')   \n",
    "        max3 = -float('inf')   \n",
    "        min1 = float('inf')     \n",
    "        min2 = float('inf')       \n",
    "        for num in nums:\n",
    "            if num > max1:     \n",
    "                max3 = max2   \n",
    "                max2 = max1  \n",
    "                max1 = num \n",
    "            elif num > max2: \n",
    "                max3 = max2 \n",
    "                max2 = num \n",
    "            elif num > max3: \n",
    "                max3 = num \n",
    "            if num < min1:\n",
    "                min2 = min1\n",
    "                min1 = num\n",
    "            elif num < min2:\n",
    "                min2 = num\n",
    "        return max(max1 * max2 * max3, max1 * min1 * min2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        return max(nums[0]*nums[1]*nums[2],nums[0]*nums[-1]*nums[-2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        return max(nums[0]*nums[1]*nums[-1], nums[-3]*nums[-2]*nums[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: list[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return\n",
    "        nums.sort(reverse=True)\n",
    "        return nums[0] * nums[1] * nums[2] if nums[0] * nums[1] * nums[2] > nums[0] * nums[-1] * nums[-2] else nums[0] * nums[-1] * nums[-2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        return nums[-1] * nums[-2] * nums[-3] if nums[-1] * nums[-2] * nums[-3] > nums[-1] * nums[0] * nums[1] else nums[-1] * nums[0] * nums[1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
